1. Field Of The Invention
The present invention is a system and method for the efficient allocation and access of memory in a microcomputer.
2. Related Art
In any modern computer system, management methods for storing data play a key role in the efficient operation of the computer. Because the computer systems are becoming more complex, memory management schemes are becoming more and more important. Both the speed of accessing the data, as well as the efficient use of available memory, are critical factors to be considered when developing such schemes.
In situations where the number and size of individual data entries is unknown, a versatile memory management scheme allows the computer system to most wisely utilize precious memory. This is particularly true with schemes involving data acquisition. An example of such a scheme is a computer program which can record the purchases made in a store. A user could enter data into the program for each item bought, the name of the item, the name of the customer, and also a number of optional items such as credit card number which may or may not be filled out. Note that the size and number of data entries could not be determined beforehand. It would be wasteful to allocate a large amount of memory for each potential entry prior to entering the data, and where optional fields are not used, it would be wasteful to allocate any memory at all. Once the data has been entered, it is also of vital importance that the data can be retrieved quickly.
In finding a solution to this memory management problem, several different scheme have been devised in order to efficiently manage memory. Two conventional scheme exist, one involving the use of a table, and the other involving the use of a linked list.
The table scheme for managing memory involves the allocation of two fixed areas which are to be a pointer table and a data area. Prior to the storage of data, a fixed amount of memory is allocated by a memory management routine for use by the pointer table and data area. When memory is required for the storage of data, the data is written at the next available block of memory, and a pointer within the pointer table is given the address of this block of data. The address for what is to be the subsequent block of data is then calculated, and retained. When a request for a particular data block occurs, all that is needed is a search of the pointer table in order to find the address of the data block requested.
The problem with using the table, however, is that the pointer table and the data area need to be allocated prior to storing any data. Therefore, some fixed number of pointers and fixed number of space for the data area must be allocated. This means that if you have allocated, for example, space for 100 pointers, and it turns out that more than 100 data blocks need to be stored, there will not be enough pointers. A problem also occurs if only a few very large data blocks are allocated. In that case, only a few pointers will be used, and the memory in which the remaining unused pointers are stored will be wasted.
Another conventional scheme of memory allocation which allocates memory more efficiently than a table is known as a linked list. In this scheme, rather than having a table for keeping pointers for each data block, a designated portion of each allocated data block is used as a pointer to the next block of data to be used. Thus, a pointer is only allocated when a new data block is created. As an example of this methodology, if there are two blocks of data which have been allocated, the first block has a pointer which points to the second block allocated. If the second block was the last data block to be allocated, then the pointer in that data block points to the next available data memory location. In this way, a software program can follow the link of blocks of data until the desired block is obtained.
The disadvantage of the linked list scheme, however, is that it takes a long time to find the block of data which is desired. For example, if the desired block is at the end of a long linked list of data blocks, then the software application searching for that block of data must traverse the entire length of the linked list before it obtains the desired data.
In summary, both conventional memory allocation schemes (table and linked list) have deficiencies. Table requires pointers and wastes memory space, whereas linked list is more memory efficient but data retrieval is often slower.
Thus, what the inventor realized was needed is a memory management scheme which can efficiently allocate memory (in terms of space) as is the case in a linked list, and also has the ability to quickly find desired blocks of data, as is the case with a table.